#include <stdio.h>
#include <stdlib.h>
#include <omp.h>
#include <time.h>
//gcc -std=c99 -fopenmp merge.c -o cmake-build/merge && export OMP_NUM_THREADS=24 && time ./cmake-build/merge

void merge(int arr[],int l,int m,int r)
{
    //printf("%d:%d working\n",omp_get_thread_num(),omp_get_num_threads());
    //printf("%d\n",omp_in_parallel());
    int *tmp=(int*)malloc((r-l+1)*sizeof(int));
    
    int ll=l;
    int lr=m;
    int rl=m+1;
    int rr=r;
    
    int k=0;
    for(k=0;ll<=lr&&rl<=rr;k++)
    {
        if(arr[ll]<=arr[rl])
        {
            tmp[k]=arr[ll++];
        }
        else
        {
            tmp[k]=arr[rl++];
        }
    }
    
    if(ll<=lr)
    {
        for(int i=ll;i<=lr;i++)
            tmp[k++]=arr[i];
    }
    
    if(rl<=rr)
        for(int i=rl;i<=rr;i++)
            tmp[k++]=arr[i];
    
    for(int i=0;i<r-l+1;i++)
        arr[l+i]=tmp[i];
    free(tmp);
}

void merge_sort(int data[],int l,int r)
{
    if(l<r)
    {
        int m=(l+r)/2;
        #pragma omp parallel shared(data,l,m,r) default(none)
        {
            #pragma omp sections
            {
                #pragma omp section
                merge_sort(data,l,m);
                #pragma omp section
                merge_sort(data,m+1,r);
            }
        }
        merge(data,l,m,r);
    }
}

int main()
{
    //static const int N=(int)1e12;
    //static const int N=(int)1e9;
    static const int N=(int)1e4;
    
    int     *a=(int*)malloc(N*sizeof(int));
    for(int i =0;i<N;++i)
        a[i]=rand();
    
    clock_t start=clock();
    merge_sort(a,0,N-1);
    double time=(double)(clock()-start)/CLOCKS_PER_SEC;
    printf("%d %lfs\n",N,time);
    
    free(a);
    return 0;
}